package com.ricky.core.quad;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public class QuadTree<T> {

	/**
	 * 得到坐标点周围n格的叶子
	 * 参数:</br>
	 * <b>row:uint</b> (行)</br>	
	 * <b>col:uint</b> (列)</br>
	 * <b>radius:uint</b> 半径</br>		
	 */
	public List<T> getAroundLeaf(int row,int col,int radius)
	{
		int y1;int y2; int x1; int x2;
		
		x1=row-radius;
		y1=col-radius;
		x2=row+radius;
		y2=col+radius;
		if(x1<0)x1=0;
		if(y1<0)y1=0;
		
		Leaf<T> leaf;
		List<T> item;
		List<T> result=new ArrayList<T>();
		int m;
		for(int i=y1;i<=y2;i++)
		{
			for(int j=x1;j<=x2;j++)
			{
				m=Morton.morton(i,j);
				System.out.println(m);
				leaf=_tree.get(m);
				if(leaf!=null)
				{
					item=leaf.getObjs();
					if(item!=null)
					{
						for(int mo=0;mo<item.size();mo++)
						{
							if(result.indexOf(item.get(mo))==-1)
							{
								result.add(item.get(mo));
							}
						}
						
					}
				}
//					result.add(leaf.getObjs());
			}
		}
		
		return result;
	}
	
	/**
	 * 得到格子区域内的所有对象</br>
	 * 参数:</br>
	 * <b>x1:int</b> (列)垂直开始格子索引</br>
	 * <b>y1:int</b> (行)水平开始格子索引</br>	
	 * <b>x2:int</b> (列)垂直结束格子索引</br>	
	 * <b>y2:int</b> (行)水平结束格子索引</br>	
	 */
	public List<T> getArea(int x1,int y1,int x2,int y2)
	{
		List<T> item;
		List<T> result=new ArrayList<T>();
		int m;
		Leaf<T> leaf;
		for(int i=y1;i<=y2;i++)
		{
			for(int j=x1;j<=x2;j++)
			{
				m=Morton.morton(i,j);
				leaf=_tree.get(m);
				if(leaf!=null)
				{
					item=leaf.getObjs();
					if(item!=null)
					{
						for(int mo=0;mo<item.size();mo++)
						{
							if(result.indexOf(item.get(mo))==-1)
							{
								result.add(item.get(mo));
							}
						}
						
					}
				}
			}
		}
		
		return result;
	}
	
	/**
	 * 通过一维数组创建树
	 * 参数</br>
	 * arr:Array 一维数组
	 * length:int 一维数组宽度
	 */
	public void buildTreeBySingleArray(byte[] arr,int maxWidth)
	{
		//Boolean traversable;
		int y=0;int x=0;Leaf<T> l;int arrLen;int m;
		arrLen=arr.length;
		int att=0;
		for(int i=0;i<arrLen;i++)
		{
			att=arr[i];
			x=i % maxWidth;
			y=i/maxWidth;

			m=Morton.morton(y,x);
			l=_tree.get(m);
			if(l==null)
			{
				l=new Leaf<T>();
				_tree.put(m, l);
			}
//			l.x=x;
//			l.y=y;
			l.setAtt(att);
//			l.traversable=traversable;
		}
		
	}
	
	/**
	 * 创建树
	 * 参数</br>
	 * arr:Array 二维数组
	 */
	public void buildTree(byte[][] arr)
	{
//		_tree=new Dictionary();
		int a0,a1,a2,a3;
		Leaf<T> l;
		int item=arr[0].length;
		int m;
		for(int i=0;i<arr.length;i++) //行
		{
			for(int j=0;j<item;j++)//列
			{
				a0=arr[i][j];				
				l=new Leaf<T>();
				l.setAtt(a0);
				m=Morton.morton(i,j);	
				_tree.put(m, l);	
			}			
		}
	}

	/**
	 * 从节点中删除游戏对象
	 * @param game:Pu 游戏对象
	 */
	public Boolean remove(T obj,int morton)
	{
		Leaf<T> l=_tree.get(morton);
		if(l!=null)
		{
			return l.remove(obj);
		}
		return false;
	}
	
	/**
	 * 将游戏对象添加到节点
	 * @param game:Pu 游戏对象
	 */
	public T add(T obj,int morton)
	{
		Leaf<T> l=_tree.get(morton);
		if(l==null)
		{
			l=new Leaf<T>();
			_tree.put(morton, l);
		}

		l.add(obj);

		return obj;
	}
	//
	private Map <Integer,Leaf<T>> _tree=new ConcurrentHashMap<Integer,Leaf<T>>();
}
